from collections import Counter
from typing import List


class Solution:
    """
    方法：使用回溯算法在二维字符网格中搜索单词
    Args:
        board: List[List[str]] - 二维字符网格
        word: str - 要搜索的单词
    Returns:
        bool - 是否在网格中找到该单词
    Time: O(M*N*3^L) - M和N是网格的行列数，L是单词长度。每个位置最多有3个方向（不能回头）搜索，最多搜索L层
    Space: O(L) - 递归调用栈的深度，最坏情况下等于单词长度L
    """
    def exist(self, board: List[List[str]], word: str) -> bool:
        cnt = Counter(c for row in board for c in row)
        if not cnt >= Counter(word):
            return False
        if cnt[word[-1]] < cnt[word[0]]:
            word = word[::-1]
        m, n = len(board), len(board[0])
        def backtrack(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]: # 匹配失败
                return False
            if k == len(word) - 1: # 匹配成功！
                return True
            board[i][j] = ''  # 标记访问过
            for x, y in (i, j-1), (i, j+1),(i-1, j), (i+1, j):  # 相邻格子
                if 0 <= x < m and 0 <= y < n and board[x][y] != '' and backtrack(x, y, k + 1):
                    return True
            board[i][j] = word[k] # 恢复现场
            return False # 没搜到
        return any(backtrack(i, j, 0) for i in range(m) for j in range(n))